package tianhao.luo.binarysorttree;

/**
 * @author: tianhao.luo@hand-china.com 2021/6/27  上午9:26
 */
public class Node {
    public int value;

    public Node left;

    public Node right;

    public Node(int value) {
        this.value = value;
    }

    // 添加结点的方法

    /**
     * 添加结点的方法
     * @param node 结点
     */
    public void add(Node node){
        if (node == null){
            return;
        }

        // 判断传入的结点和根节点的支
        if (node.value<this.value){
            // 当前结点的左子节点为null
            if (this.left == null){
                this.left = node;
            }else {
                // 递归向左子树添加
                this.left.add(node);
            }
        }

        if (node.value>=this.value){
            // 当前结点的右子节点为null
            if (this.right == null){
                this.right = node;
            }else {
                this.right.add(node);
            }
        }
    }

    public void infixOrder(){
        if (this.left !=null){
            this.left.infixOrder();
        }

        System.out.println(this);

        if (this.right !=null){
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("Node{");
        sb.append("value=").append(value);
        sb.append('}');
        return sb.toString();
    }


    /**
     * 查找要删除的结点
     * @param value 需要删除的结点的值
     * @return 如果找到返回该结点,否则返回null
     */
    public Node searchNode(int value){
        // 找到该节点
        if (value == this.value){
            return this;
        }else if (value < this.value){
            // 查找的值小于当前结点的值
            // 需要左子树递归查找
            // 如果左子节点为空
            if (this.left == null){
                return null;
            }
            return this.left.searchNode(value);
        }else {
            // 如果查找的值不小于当前节点,向右子树递归查找
            if (this.right == null){
                return null;
            }
            return this.right.searchNode(value);
        }
    }


    /**
     * 查找要删除结点的父节点
     * @param value 要删除的结点值
     * @return 返回父节点
     */
    public Node searchParent(int value){
        // 当前结点是否为父节点
        if (this.left !=null && this.left.value==value){
            return this;
        }else if (this.right !=null && this.right.value ==value){
            return this;
        }else {
            // 查找的值小于当前结点的值,并且当前结点的左子节点不为空
            if (value < this.value && this.left !=null){
                return this.left.searchParent(value);
            }else if (value >= this.value && this.right !=null){
                return this.right.searchParent(value);
            }else {
                // 没有找到父节点
                return null;
            }
        }
    }
}
